#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//int main()
//{
//    char arr1[20]="abcdef";
//    char arr2[20]="ghi";
//    strcat(arr2,arr1);
//    printf("%s\n",arr2);
//    return 0;
//}

//int main()
//{
//    int a[10];
//    for(int i=0;i<10;i++){
//        scanf("%d",&a[i]);
//    }
//
//    int min=a[0];
//
//    for(int i=0;i<10;i++){
//        if(a[i]<min){
//            min=a[i];
//        }
//    }
//    printf("%d\n",min);
//
//    return 0;
//}

//int main()
//{
//    char arr1[10]="abcd";
//    char arr2[10]="abcd";
//    int n=strcmp(arr2,arr1);
//    printf("%d\n",n);
//    return 0;
//}


//int main()
//{
//    int a[10];
//    for(int i=0;i<10;i++){
//        scanf("%d",&a[i]);
//    }
//
//    int b=0,s=0;
//    int min=a[0],max=a[0];
//
//    for(int i=0;i<10;i++){
//        if(a[i]<min){
//            min=a[i];
//            s=i;
//        }
//        if(a[i]>max){
//            max=a[i];
//            b=i;
//
//        }
//    }
//
//    int t=0;
//    t=a[b];
//    a[b]=a[s];
//    a[s]=t;
//
//    for(int i=0;i<10;i++){
//        printf("%d ",a[i]);
//    }
//
//    return 0;
//}

//int main()
//{
//    int a[10];
//    int i=0;
//    for( i=0;i<9;i++){
//        scanf("%d",&a[i]);
//    }
//
//    int n=0;
//    scanf("%d",&n);
//
//    for( i=8;i>=0&&a[i]<n;i--){
//        a[i+1]=a[i];
//    }
//
//    a[i+1]=n;
//
//    for( i=0;i<10;i++){
//        printf("%d ",a[i]);
//    }
//
//    return 0;
//}


//int main()
//{
//    int a[100];
//    int n=0,maxcount=0,k=-1;
//    scanf("%d",&n);
//
//    for(int i=0;i<n;i++){
//        scanf("%d",&a[i]);
//    }
//
//    for(int i=0;i<n;i++){
//        int count=0;
//        for(int j=0;j<n;j++){
//            if(a[i]==a[j]){
//                count++;
//            }
//        }
//        if(count>maxcount){
//            maxcount=count;
//            k=a[i];
//        }
//    }
//
//    if(maxcount==1){
//        printf("NO");
//    }
//    else{
//        for (int i = 0; i < n; i++)
//        {
//            int count = 0;
//            for (int j = 0; j < n; j++)
//            {
//                if (a[i] == a[j])
//                {
//                    count++;
//                }
//            }
//            if (count == maxcount)
//            {
//                printf("%d ", a[i]);
//                break;
//            }
//        }
//    }
//
//    return 0;
//}

//int f(int n)
//{
//    if(n==1){
//        return 1;
//    }
//    else{
//        return n*f(n-1);
//    }
//
//}
//
//int main()
//{
//    int n=0,m=0;
//    scanf("%d %d",&m,&n);
//
//    int r=f(m)/(f(n)*f(m-n));
//
//    printf("%d",r);
//
//    return 0;
//}


//#include <stdio.h>
//#include <stdlib.h>
//#include <math.h>
//
//int main()
//{
//    char c;
//    int count=0;
//    while((c=getchar())!=EOF){
//        if(c=='$'){
//            count++;
//        }
//    }
//    printf("%d\n",count);
//    return 0;
//}

//int main()
//{
//    int a[100];
//    int n=0,sum=0;
//    scanf("%d",&n);
//    for(int i=0;i<n;i++){
//        scanf("%d",&a[i]);
//    }
//
//    for(int i=0;i<n;i++){
//        if(a[i]%2==0){
//            sum+=a[i];
//        }
//    }
//
//    printf("%d\n",sum);
//    return 0;
//}

//void del_char(char *c,char n)
//{
//    int j=0;
//    for(int i=0;i<strlen(c);i++){
//        if(c[i]!=n){
//            c[j]=c[i];
//            j++;
//        }
//    }
//    c[j]='\0';
//}
//
//int main()
//{
//    char c[100],n=0;
//
//    gets(c);
//    scanf("%c",&n);
//    del_char(c,n);
//    printf("%s\n",c);
//    return 0;
//}

//float f(int n)
//{
//    if(n==1){
//        return 1;
//    }
//    else{
//        return n*f(n-1);
//    }
//
//}
//
//int main()
//{
//    int n=0;
//    scanf("%d",&n);
//    float sum=0;
//    for(int i=1;i<=n;i++){
//        sum+=1/f(i);
//    }
//    printf("%.4f",sum);
//    return 0;
//}

//int main()
//{
//    int a[10],n=0,count=0;
//
//    for(int i=0;i<10;i++){
//        scanf("%d",&a[i]);
//    }
//
//    int sum=0;
//
//    for(int i=0;i<10;i++){
//        sum+=a[i];
//    }
//
//    float pj=(float)sum/10;
//
//    for(int i=0;i<10;i++){
//        if(a[i]>pj){
//            count++;
//        }
//    }
//
//    printf("%d\n",count);
//    return 0;
//}
//

//double mypow(int x,int n)
//{
//    if(n==1){
//        return x;
//    }
//    else{
//        return x*mypow(x,n-1);
//    }
//
//}
//
//double fact(int n)
//{
//    if(n==1){
//        return 1;
//    }
//    else{
//        return n*fact(n-1);
//    }
//}
//
//int main()
//{
//    float x=0;
//    int n=0,t=1;
//    float sum=0;
//    scanf("%f %d",&x,&n);
//
//    for(int i=1;i<=n;i++){
//        sum+=(mypow(x,n)/fact(n))*t;
//        t*=-1;
//    }
//
//    printf("%.4f",sum);
//    return 0;
//}
//
//int jdz(int a)
//{
//    if(a>=0){
//        return a;
//    }
//    else{
//        return -a;
//    }
//
//}
//
//int main()
//{
//    int a[10][10];
//    int n=0;
//    scanf("%d",&n);
//    int h=0,l=0,max=0,min=0,x=0,d=0;
//
//    for(int i=0;i<n;i++){
//        for(int j=0;j<n;j++){
//            scanf("%d",&a[i][j]);
//        }
//    }
//
//    max=jdz(a[0][0]),min=a[0][0];
//
//    for(int i=0;i<n;i++){
//        for(int j=0;j<n;j++){
//            if(jdz(a[i][j])>jdz(max)){
//                max=jdz(a[i][j]);
//                h=i+1;
//                l=j+1;
//            }
//        }
//    }
//
//    printf("%d %d %d",max,h,l);
//    return 0;
//}


















































































































































